This invention relates to data encoding and decoding of digital information transmitted over a communication channel. In particular, the invention relates to coding and iterative threshold decoding of convolutional self-doubly orthogonal codes.
In modern electronic communications, information is generally transmitted in a discrete digital format. In various applications such as wireless telephonic communications or satellite communications the transmitted information signal is susceptible to corruption due to noise in the communication channel (i.e., electronic interference in the transmission medium). To improve transmission reliability and accuracy, the prior art discloses channel coding as an error correcting technique. The two principal error correcting techniques are block and convolutional coding.
In convolutional coding, parity bits derived from a span of information bits are added to the information bits for redundancy. The information bit span length is called the constraint length. Convolutional codes usually operate over long streams of information bits, which could be broken into shorter blocks. Whether or not broken into blocks, the streams of information bits are encoded in a continuous manner by a simple linear apparatus called a convolutional encoder.
In a basic convolutional encoder, the encoder encodes a stream of information bits by breaking the information stream into blocks of N information bits and by performing a logical exclusive-or operation on the most recently received N bit block. For systematic convolutional encoders, the resulting parity bit from the encoder's calculation is appended for redundancy to the information bits before transmission. Therefore, the final transmitted message will consist of the most recently received information bits and the parity bit output of the logical exclusive-or operation.
Variations of this simple form includes convolution encoders in which, for example, the encoder calculates parity bits from the most recently received eight bit information block and selected information bits of pervious blocks. The encoder's coding rate (i.e., the number of information bits per parity bits) may also be adjusted to improve reliability or accuracy of the decoded information.
Self-orthogonal convolutional codes are specific types of convolutional codes. In self orthogonal convolutional code the transmitted parity bits corresponding to each transmitted information bit are generated by the encoder in such a way that no two parity equations include more than one symbol in common. As a consequence, for decoding, a simple majority rule on the parity equations can be implemented for obtaining an estimate on each received information bit.
In order to further improve the reliability of the transmitted data, several techniques based on multi-level coding and utilizing the serial or parallel concatenation of codes have been developed. Turbo encoding is one such technique. Turbo encoding may be regarded as encoding the information sequence twice, once using a first encoder, and then, using a second encoder but operating on a scrambled or interleaved version of the same sequence. In principle, any number of encoders separated by random interleavers may be used, but the structure is usually limited to two encoders with a single interleaver between them. In these techniques the convolutional codes are generally of the recursive systematic type, that is, the information bits are not altered by the encoding process and are transmitted along the encoded accompanying redundant symbols. A key to the improved performance of the Turbo coding technique is that because of the interleaving or scrambling between each successive encoder operation, each encoder appears to operate on a set of independent information data.
As to decoding, convolutional codes may be decoded using the well-known methods of maximum likelihood sequence estimation techniques such as the Viterbi algorithm. Another well-known decoding technique which is especially well suited for self-orthogonal convolutional codes is threshold decoding. Threshold decoding may be implemented with or without feedback and with a hard or soft quantized input.
Generally, decoding of Turbo codes is performed in iterations of two steps. On the first step, the first decoder operates on the soft output of the channel pertaining to the code symbols of the first encoder, and provides to the second decoder information on the reliability of the decoded sequence. Likewise, the second decoder operates on the interleaved version of the estimated information sequence it receives from the first decoder together with a reliability information measure on that sequence and its appropriate code symbols. The process is repeated iteratively whereby the second decoder feeds back soft output reliability information to the first decoder and the process may be repeated anew any number of times. As in the encoding, the interleaving or scrambling allows iterative decoding to be performed over a set of uncorrelated observables.
More specifically, two decoding methods for Turbo Codes have been considered. The symbol-by-symbol Maximum A Posteriori Probability, MAP, algorithm due to Bahl, et al., "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rates", IEEE Transactions on Information Theory, Vol. IT-20, March 1976, and the Soft-Input Soft-Output Viterbi decoding algorithm, SOVA. See U.S. Pat. No. 4,811,346 issued to Battail and U.S. Pat. No. 5,537,444 issued to Nill, et al. Both of these decoding algorithms suffer from a rather large computational complexity which prompted the development of some simplifying variants. In addition to the decoding complexity, Turbo Codes present the further disadvantage of an inherent latency or delay which is due to the presence of an interleaver and the number of iterations that are required to achieve a given error probability. This delay may be quite large, even unacceptable to many delay-sensitive applications. In some applications such as encountered in wireless communications for example, both the decoder complexity and latency conspire to make the traditional Turbo coding technique unsuitable.
Accordingly, it is an object of the present invention to provide a novel and improved encoder and decoder based on using convolutional self doubly orthogonal codes together with iterative threshold-type decoding.
It is another object of the present invention to provide novel iterative encoders and decoders for convolutional codes without increased complexity and latency caused by interleaving.
It is yet another object of the present invention to provide novel iterative hard or soft quantized decoders based on Turbo decoders without interleaving or scrambling.
It is still another object of the present invention to provide a novel iterative feedback decoder for convolutional codes with error propagation constrained by the coding scheme and weighing of feedback decisions.
These and many other objects and advantages of the present invention will be readily apparent to one skilled in the art to which the invention pertains from a perusal of the claims, the appended drawings, and the following detailed description of the preferred embodiments.